#include "Sort.h"

//交换
void Swap(int *p1,int *p2)
{
    int x = *p1;
    *p1 = *p2;
    *p2 = x;
}

// 插入排序：直接插入排序，希尔排序
// 直接插入排序:升序
// 最坏：O(N^2)     逆序
// 最好：O(N)       顺序有序
/*
    思路：
    第一步：从第1项开始i，与前面的数据第0项开始比较，保存第1项数据tmp
    第二步：如果第1项比第0项小，则将第0项数据向后挪移
    第三步：将保存下的第1项数据放入原本第0项数据的位置
    第四步：i向后+1，重复第一，二，三步，直到i < size
*/
void InsertSort(int* arr,int size)       //*a是数组，n是数组长度
{
    for(int i = 1;i < size;i++)
    {
        int end = i-1;
        int tmp = arr[i];
        // 将tmp插入到[0,end]区间中，保持有序
        while(end >= 0)
        {
            // 升序用小于
            // 降序用大于
            if(tmp < arr[end])
            {
                arr[end+1] = arr[end];
                end--;
            }
            else
                break;
        }
        arr[end+1] = tmp;
    }

    // Print(arr,size);
}
// 希尔排序：直接插入排序的优化
/*
    思路：
    第一步：选定一个数字gap，将数组从0开始按照距离gap划分
    第二步：将各个组内按照直接插入排序进行排序
    第三步：排序之后，重新选定gap，重复1，2步骤，直到gap等于1，将数组内数据进行统一排序
*/
//时间复杂度：O(n^1.3)
void ShellSort(int* arr,int size)
{
    // //预排序
    // int gap = 3;
    // for(int j = 0;j < gap ; j++)
    // {
    //     for (int i = 0; i < size - gap; ++i) 
    //     {
    //         //一趟
    //         int end = i;
    //         int tmp = arr[end + gap];
    //         while (end >= 0) 
    //         {
    //             if (tmp < arr[end]) 
    //             {
    //                 arr[end + gap] = arr[end];
    //             } 
    //             else 
    //             {
    //                 break;
    //             }
    //             end-=gap;
    //         }
    //         arr[end + gap] = tmp;
    //     }
    // }

    // gap > 1 预排序
    // gap == 1 直接插入排序
    int gap = size / 2;
    // int gap = size / 3 + 1;
    while(gap >= 1)
    {
        // 最开始gap很大，gap = size/3+1 or size/2      时间复杂度为O(n)
        // 最后gap很小，gap = 1         时间复杂度为O(n)
        for(int i = 0;i < size-gap;i++)
        {
            int end = i;
            int tmp = arr[i+gap];
            while(end >= 0)
            {
                if(tmp < arr[end])
                {
                    arr[end + gap] = arr[end];
                    end -= gap;
                }
                else
                    break;
            }
            arr[end + gap] = tmp;
        }
        // printf("gap:%d\n",gap);
        // Print(arr,size);
        gap = gap / 2;
        // gap = gap / 3 + 1;
    }

    // Print(arr,size);
}

// 选择排序：直接选择排序，堆排序
// 直接选择排序：升序
/*
    思路：
    第一步：首先选出一个最大值和最小值(可任意选)
    第二步：在将最大值和最小值向后依次遍历比较，若是比最大值大，比最小值小，则将它们更新
    第三步：将最大值和最小值依次放入两边，再将范围向中间缩小
    按照这样的步骤循环，直到无法可缩小结束
*/
// 最好：时间复杂度为O(N^2)
// 最坏：时间复杂度为O(N^2)
void SelectSort(int* arr,int size)
{
    //一次选两个数：选最大数和最小数
    int left = 0,right = size - 1;
    
    while(left < right)
    {
        int mini = left,maxi = left;
        for(int i = left + 1;i <= right;i++)
        {
            if(arr[i] < arr[mini])
                mini = i;
            if(arr[i] > arr[maxi])
                maxi = i;
        }
        Swap(&arr[left],&arr[mini]);

        // 如果left和maxi重叠，交换后修正一下
        if(left == maxi)
            maxi = mini;
        Swap(&arr[right],&arr[maxi]);
        left++;
        right--;
    }

    // //一次选一个数：选最大数或最小数
    // int left = 0;
    // while(left < size)
    // {
    //     int mini = left;
    //     for(int i = mini + 1;i < size;i++)
    //     {
    //         if(arr[mini] > arr[i])
    //             mini = i;
    //     }
    //     Swap(&arr[mini],&arr[left]);
    //     left++;
    // }

    // Print(arr,size);
}
//堆排序
/*
    思路：
    第一步：将这个数组调整为大堆或小堆
    若是排升序，则建大堆（即首位值最大）
    若是排降序，则建小堆（即首位值最小）

    第二步：将首位和末尾的数互换位置，数组尺寸-1，再将此时的首位值向下调整，循环往复
    详细步骤：
    从末尾开始，和第一个数字换位置，因为第一个数字是最大或最小的
    交换完后，暂时舍弃最后一个数，将此时的第一个数字向下调整，即：将此时堆中的最大值或最小值提到首部
    调整完后，此时首位的数字又是最大值或最小值
    按照这个步骤循环往复，将这个堆进行排序，便是堆排序
*/
//时间复杂度为O(N*logN)
//向上调整
//前提：除了child这个位置，前面数据构成堆
void AdjustUp(int* arr,int child)
{
    int parent = (child-1)/2;
    while(child > 0)
    {
        if(arr[child] > arr[parent])
        {
            Swap(&arr[child],&arr[parent]);
            child = parent;
            parent = (child-1)/2;
        }
        else
            break;
    }
}
//向下调整
//前提：左右子树都是大堆/小堆
void AdjustDown(int* arr,int size,int parent)
{
    int child = parent*2+1;
    while(child < size)
    {
        //选出左右孩子中大的那个（小根堆则相反）
        //这两个条件不可交换，即先判断是否存在，后判断大小
        if(child + 1 < size && arr[child] < arr[child + 1])
            child++;
        if(arr[child] > arr[parent])
        {
            Swap(&arr[child],&arr[parent]);
            parent = child;
            child = parent*2+1;
        }
        else
            break;
    }
}
//排升序 -- 建大堆
//排降序 -- 建小堆
void HeapSort(int* arr,int size)
{
    // //第一步：将这个数组调整为大堆或小堆
    // //若是排升序，则建大堆（即首位值最大）
    // //若是排降序，则建小堆（即首位值最小）

    // //向上调整建堆 -- 时间复杂度为O(N*logN)
    // for(int i = 1;i < NUM;i++)
    // {
    //     AdjustUp(heap,i);
    // }

    //建堆 -- 向下调整建堆 -- 时间复杂度为O(N)
    // size - 1 - 1:第一个1是下标减1，指向最后一个数据，第二个1是由于公式child=parent*2+1指向的双亲结点的左孩子结点
    for(int i = (size-1-1)/2;i >= 0;i--)
        AdjustDown(arr,size,i);

    // 第二步：将首位和末尾的数互换位置，数组尺寸-1，再将此时的首位值向下调整，循环往复
    // 详细步骤：
    // 从末尾开始，和第一个数字换位置，因为第一个数字是最大或最小的
    // 交换完后，暂时舍弃最后一个数，将此时的第一个数字向下调整，即将此时堆中的最大值或最小值提到首部
    // 调整完后，此时首位的数字又是最大值或最小值
    // 按照这个步骤循环往复，将这个堆进行排序，便是堆排序
    int end = size - 1;
    while(end > 0)
    {
        Swap(&arr[end],&arr[0]);
        AdjustDown(arr,end,0);
        end--;
    }

    // Print(arr,size);
}

// 交换排序：冒泡排序，快速排序
/*
    将相邻的两个数进行比较，符合条件就交换，注意交换时的边界位置
*/
// 最好：O(N^2)
// 最坏：O(N)
void BubbleSort(int* arr,int size)
{
    for(int i = 0;i < size;i++)
    {
        bool exchange = false;
        for(int j = 1;j < size - i;j++)
        {
            if(arr[j - 1] > arr[j])
            {
                Swap(&arr[j],&arr[j - 1]);
                exchange = true;
            }
        }
        if(exchange == false)
            break;
    }
    // Print(arr,size);
}
// 快速排序：升序
/*
    思路：
    第一步：选择最左边或最右边数为基准值keyi(这里假设最左边的值为基准值)，将大于基准值的数换到右边，小于基准值的数换到左边
    第二步：先从最右边right开始向左边走，若是有小于基准值的数便暂停，再从最左边left开始向右边走，若是有大于基准值的数便暂停
    第三步：当他们暂停时，则交换位置，直到left > right，此时left等于right且keyi绝对比left小，所以将基准值keyi和left交换，此时基准值的左边小于该值，右边大于该值
    第四步：此时将left或right的值赋给keyi
    开始递归
    将数组划分
    第一次划分的前半部分：begin到keyi-1，后半部分：keyi到end
    以此类推：每次划分的部分都会为上层/2的数量，直到只剩一个数字
    操作上面四个步骤，直到left >= right，即只剩一个数字，开始返回结果
*/
int GetMidNumi(int* arr,int left,int right)
{
    int mid = (left+right)/2;
    if(arr[left] < arr[mid])
    {
        if(arr[mid] < arr[right])
            return mid;
        else if(arr[left] > arr[right])
            return left;
        else
            return right;
    }
    else    // arr[left] > arr[mid]
    {
        if(arr[mid] > arr[right])
            return mid;
        else if(arr[left] > arr[right])
            return right;
        else
            return left;
    }
}
// hoare版本
int PartSort1(int* arr,int left,int right)
{
    // 最好：时间复杂度O(N*logN)
    // 最坏(有序的情况下)：时间复杂度O(N^2)
    // 加了优化(随机选数或者三数(左中右)取中)后，时间复杂度都为O(N^2)

    // // 随机选keyi
    // int randi = left + (rand() % (right - left));
    // // 加left的作用是为了防止选取的随机数在左半部分
    // Swap(&arr[left],&arr[randi]);

    // 三数取中
    int midi = GetMidNumi(arr,left,right);
    Swap(&arr[left],&arr[midi]);

    int keyi = left;    
    while(left < right)
    {
        //注意：若是左边的值为keyi，则右边先走，否则相反
        while (left < right && arr[right] >= arr[keyi])
            --right;
        while(left < right && arr[left] <= arr[keyi])
            ++left;
        
        Swap(&arr[left],&arr[right]);
    }
    Swap(&arr[left],&arr[keyi]);
    keyi = left;

    return keyi;
}
// 挖坑法：升序
/*
    思路：在hoare版本的基础之上，
    第一步，先确定基准值keyi，并保存该值tmp
    第二步，若是keyi在左边，则右边先走，直到找到比tmp小的值，将该值赋给左边
    第三步，再从左边走，直到找到比tmp大的值，将该值赋给右边
    循环第二，三步，直到left等于right，此时再将tmp的值赋给它们相遇的位置
    再进入递归，以下和hoare版本相同
*/
int PartSort2(int* arr,int left,int right)
{
    // 三数取中
    int midi = GetMidNumi(arr,left,right);
    Swap(&arr[left],&arr[midi]);

    int key = arr[left];  
    int hole = left;

    while(left < right)
    {
        //注意：若是左边的值为keyi，则右边先走，否则相反
        while (left < right && arr[right] >= key)
            --right;
        arr[hole] = arr[right];
        hole = right;

        while(left < right && arr[left] <= key)
            ++left;
        arr[hole] = arr[left];
        hole = left;
    }
    arr[hole] = key;

    return hole;
}
// 前后指针法：升序
/*
    思路：定义两个指针prev和cur，一前cur一后prev
    cur向右找比keyi小的值，
    若是cur找到比keyi小的值时，prev下一个指向的一定是比keyi大的数，再++prev判断和cur是否相等
    如果相等，就没必要交换，cur指向的数和prev指向的数交换，再++cur
    若是cur找到比keyi大的值时，便++cur
*/
int PartSort3(int* arr,int left,int right)
{
    // 三数取中
    int midi = GetMidNumi(arr,left,right);
    Swap(&arr[left],&arr[midi]);

    int keyi = left;

    int prev = left;
    int cur = left + 1;
    while(cur <= right)
    {
        // ++prev != cur的作用是为了判断它们是否相等，如果相等就没有必要交换
        if(arr[cur] < arr[keyi] && ++prev != cur)
            Swap(&arr[cur],&arr[prev]);
        ++cur;
    }
    Swap(&arr[keyi],&arr[prev]);
    keyi = prev;

    return keyi;
}
void QuickSort(int* arr,int left,int right)
{
    if(left >= right)
        return;
    
    // 小区间优化 -- 小区间直接使用插入排序
    if((right-left+1) > 10)     //+1的原因：例如 right=0,left=9,确保数组中有10个数
    {
        int keyi = PartSort3(arr,left,right);
        QuickSort(arr,left,keyi-1);
        QuickSort(arr,keyi+1,right);
    }
    else
    {
        InsertSort(arr+left,right-left+1);
    }
}
//快速排序非递归
/*
    思路：利用数据结构中的栈
    循环条件：判断栈中是否为空
    判断条件：子区间只有一个值或者不存在就不如栈
    第一步：将左右下标(区间)分别进进栈（因为先进先出，所以先右再左），进入循环条件开始循环
    第二步：将左右下标(区间)分别取出，按照该区间范围进行单趟排序，结束后，返回的keyi则为它们的中间分割值
    第三步：按照[begin,keyi-1] keyi [keyi+1,end]这个范围将区间进行划分
    重复以上步骤，直到栈为空
*/
void QuickSortNonR(int* arr,int left,int right)
{
    ST st;
    STInit(&st);
    STPush(&st,right);
    STPush(&st,left);
    while(!STEmpty(&st))
    {
        int begin = STTop(&st);     //left
        STPop(&st);
        int end = STTop(&st);       //right
        STPop(&st);

        int keyi = PartSort3(arr,begin,end);
        // [begin,keyi-1] keyi [keyi+1,end]
        if(begin < keyi - 1)
        {
            STPush(&st,keyi-1);
            STPush(&st,begin);
        }
        if(keyi + 1 < end)
        {
            STPush(&st,end);
            STPush(&st,keyi + 1);
        }
    }

    STDestroy(&st);
}
// 归并排序
/*
    思路：将数组进行划分，按顺序排列，最后返回
    第一步：将数组进行划分，[begin,mid][mid+1,end]，直到begin >= end
    第二步：将递归划分出的区间进行两两比较，按顺序赋给另一数组，用于暂存结果，再将结果交回原数组
    按照此过程以此类推，直到栈中为空
    此过程类似于二叉树的后序遍历
*/
void _MergeSort(int* arr,int begin,int end,int* tmp)
{
    if(begin >= end)
        return;
    int mid = (begin+end)/2;
    
    // [begin,mid][mid+1,end]，子区间递归排序
    _MergeSort(arr,begin,mid,tmp);
    _MergeSort(arr,mid+1,end,tmp);

    // [begin,mid][mid+1,end] 归并
    int begin1 = begin,end1 = mid;
    int begin2 = mid+1,end2 = end;
    int i = begin;
    while(begin1 <= end1 && begin2 <= end2)
    {
        if(arr[begin1] <= arr[begin2])
            tmp[i++] = arr[begin1++];
        else
            tmp[i++] = arr[begin2++];
    }

    while(begin1 <= end1)
        tmp[i++] = arr[begin1++];
    while(begin2 <= end2)
        tmp[i++] = arr[begin2++];
    
    memcpy(arr+begin,tmp+begin,sizeof(int)*(end-begin+1));
}
void MergeSort(int* arr,int size)
{
    int* tmp = (int*)malloc(sizeof(int)*size);
    if(tmp == NULL)
    {
        perror("malloc fail");
        return;
    }

    _MergeSort(arr,0,size-1,tmp);

    free(tmp);
}
// 归并排序非递归
/*
    思路：按照归并排序的递归思路来说，将数组利用递归划分为n个数据，依次进行比较(先一一比较，再两两比较，或者两三比较等等)
        每一次比较都会将比较结果送到临时数组中，该层递归结束便送回原数组中
        而非递归则不必进行划分，直接从一一比较开始，同样送到临时数组中，每一次比较完后都将数据送回原数组
        限制条件：划分的数据距离gap < 数组长度size
        每一次比较结束后，将i += gap*2是为了将这一层的数据都进行比较
        需要注意的是：它们的边界划分，它们的边界每一次都会进行改变，以及越界后的处理方式
        边界划分：分出的两个边界是相邻的，所以可以定义[begin1,end1][begin2,end2] 即[i,i+gap-1][i+gap,i+2*gap-1]
        其中end1,begin2,end2是会越界的，需要对他们进行限制
    限制方法一：
        当end1和begin2越界时，直接结束本次循环，后面也不会再拷贝没有排好序或者无用的数据
        当end2越界时，可让它指向最后一个数据
    限制方法二：
        当end1越界时，让它指向最后一个数据，此时begin2和end2同样越界了，使它们指向一个不存在的数组，如[4,2]使他们无法进行循环进行赋值
        当begin2越界时，end2也一样越界了，同样指向一个不存在的数组
        当end2越界时，可让它指向最后一个数据
    推荐使用方法一，因为方法二越界后，会拷贝一些没有排好序的数据，方法一归并排序一次便拷贝一次，更为节省时间
    同样在拷贝时，要注意拷贝时机，若是使用限制方法一，便在值赋给临时数组后，便将数据拷贝回原数组(即归并一部分，拷贝一部分)
    若是使用限制方法二，便在间距为gap的多组数据，归并完以后，一把拷贝
*/
void MergeSortNonR(int* arr,int size)
{
    int* tmp = (int*)malloc(sizeof(int)*size);
    if(tmp == NULL)
    {
        perror("malloc fail");
        return;
    }

    int gap = 1;
    while(gap < size)
    {
        // 间距为gap的多组数据归并
        for(int i = 0;i < size;i += 2*gap)
        {
            // 边界划分
            int begin1 = i,end1 = i+gap-1;
            int begin2 = i+gap,end2 = i+2*gap-1;
            int j = i;

            // 限制方法一：越界直接退出，本次不再拷贝
            if(end1 >= size || begin2 >= size)
                break;
            if(end2 >= size)
                end2 = size - 1;

            // //限制方法二：遇到越界进行调整，继续拷贝
            // if(end1 >= size)
            // {
            //     end1 = size - 1;
            //     begin2 = size;
            //     end2 = size-1;
            // }
            // else if(begin2 >= size)
            // {
            //     begin2 = size;
            //     end2 = size - 1;
            // }
            // else if(end2 >= size)
            // {
            //     end2 = size - 1;
            // }

            // printf("修正后：[%d,%d][%d,%d]\n",begin1,end1,begin2,end2);
            
            while(begin1 <= end1 && begin2 <= end2)
            {
                if(arr[begin1] <= arr[begin2])
                    tmp[j++] = arr[begin1++];
                else
                    tmp[j++] = arr[begin2++];
            }

            while(begin1 <= end1)
                tmp[j++] = arr[begin1++];
            while(begin2 <= end2)
                tmp[j++] = arr[begin2++];

            // 归并一部分，拷贝一部分
            memcpy(arr+i,tmp+i,sizeof(int)*(end2-i+1));
        }

        // // 间距为gap的多组数据，归并完以后，一把拷贝
        // memcpy(arr,tmp,sizeof(int)*size);

        gap *= 2;
    }
}
// 非比较排序
// 计数排序
/*
	思路：
    第一步：确定范围，防止开出过多空间
    第二步：开辟空间，存储数据的重复次数
    第三步：计算数据的重复次数保存到开辟的空间中
    第四步：按照数据的重复次数，从小到大的顺序返回原数组
    总结：计数排序适合范围集中，且范围不大的整型数组排序，不适合范围分散或者非整型排序，如：字符串、浮点数等
*/
// 时间复杂度：O(N+range)
// 空间复杂度：O(range)
void CountSort(int* arr,int size)
{
    // 确定范围，防止开出过多空间
    int max = arr[0],min = arr[0];
    for(int i = 0;i < size;i++)
    {
        if(arr[i] > max)
            max = arr[i];
        if(arr[i] < min)
            min = arr[i];
    }
    int range = max-min+1;

    // 开辟空间，存储数据的重复次数
    int* tmp = (int*)malloc(sizeof(int)*range);
    if(tmp == NULL)
    {
        perror("malloc fail\n");
        return;
    }
    memset(tmp,0,sizeof(int)*range);

    // 计数
    for(int i = 0;i < size;i++)
    {
        // arr[i] - min = i
        tmp[arr[i]-min]++;
    }

    // 排序
    int j = 0;
    for(int i = 0;i < range;i++)
    {
        while(tmp[i]--)
        {
            // i + min = arr[i]
            arr[j++] = i + min;
        }
    }
}
// 打印
void Print(int *arr,int size)
{
    for(int i = 0;i < NUM;i++)
    {
        printf("%d ",arr[i]);
    }
    printf("\n");
}